PittsburghV1, France, Analysis, bibRecord, 000012

Tight Bounds on Vertex Connectivity Under Sampling

Identifieur interne : 000012 ( France/Analysis ); précédent : 000011; suivant : 000013

Tight Bounds on Vertex Connectivity Under Sampling

Auteurs : Keren Censor-Hillel [Israël] ; Mohsen Ghaffari [États-Unis] ; George Giakkoupis [France] ; Bernhard Haeupler [États-Unis] ; Fabian Kuhn [Allemagne]

Source :

ACM Transactions on Algorithms [ 1549-6325 ] ; 2017-05-29.

RBID : Hal:hal-01635743

Abstract

A fundamental result by Karger [10] states that for any $λ$-edge-connected graph with n nodes, independently sampling each edge with probability $p = Ω(log(n)/λ)$ results in a graph that has edge connectivity $Ω(λp)$, with high probability. This paper proves the analogous result for vertex connectivity, when either vertices or edges are sampled. We show that for any k-vertex-connected graph G with n nodes, if each node is independently sampled with probability $p = Ω(log(n)/k)$, then the subgraph induced by the sampled nodes has vertex connectivity $Ω(kp 2$), with high probability. If edges are sampled with probability $p = Ω(log(n)/k)$ then the sampled subgraph has vertex connectivity $Ω(kp$), with high probability. Both bounds are existentially optimal.

Url:

https://hal.inria.fr/hal-01635743

DOI: 10.1145/3086465

Affiliations:

Links toward previous steps (curation, corpus...)

to stream Hal, to step Corpus: 000641
to stream Hal, to step Curation: 000641
to stream Hal, to step Checkpoint: 000014
to stream Main, to step Merge: 000014
to stream Main, to step Curation: 000014
to stream Main, to step Exploration: 000014
to stream France, to step Extraction: 000012

Links to Exploration step

Hal:hal-01635743

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Tight Bounds on Vertex Connectivity Under Sampling</title>
<author><name sortKey="Censor Hillel, Keren" sort="Censor Hillel, Keren" uniqKey="Censor Hillel K" first="Keren" last="Censor-Hillel">Keren Censor-Hillel</name>
<affiliation wicri:level="1"><hal:affiliation type="department" xml:id="struct-425640" status="VALID"><orgName>Department of Computer Science [Haifa]</orgName>
<date type="start">2015-08-14</date>
<desc><address><addrLine>TechnionIsrael Institute of TechnologyHaifa 32000Israel</addrLine>
<country key="IL"></country>
</address>
<ref type="url">http://www.cs.technion.ac.il/</ref>
</desc>
<listRelation><relation active="#struct-84142" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-84142" type="direct"><org type="institution" xml:id="struct-84142" status="VALID">          <orgName>Technion - Israel Institute of Technology [Haifa]</orgName>
          <desc>            <address>              <addrLine>Technion City, Haifa 3200003</addrLine>
              <country key="IL"></country>
            </address>
            <ref type="url">http://www1.technion.ac.il/en</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Israël</country>
</affiliation>
</author>
<author><name sortKey="Ghaffari, Mohsen" sort="Ghaffari, Mohsen" uniqKey="Ghaffari M" first="Mohsen" last="Ghaffari">Mohsen Ghaffari</name>
<affiliation wicri:level="1"><hal:affiliation type="institution" xml:id="struct-301950" status="VALID">          <orgName>Massachusetts Institute of Technology</orgName>
          <orgName type="acronym">MIT</orgName>
          <desc>            <address>              <addrLine>77 Massachusetts Ave, Cambridge, MA 02139</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://web.mit.edu</ref>
          </desc>
        </hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Giakkoupis, George" sort="Giakkoupis, George" uniqKey="Giakkoupis G" first="George" last="Giakkoupis">George Giakkoupis</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-490904" status="VALID"><idno type="RNSR">200718348T</idno>
<orgName>As Scalable As Possible: foundations of large scale dynamic distributed systems</orgName>
<orgName type="acronym">ASAP</orgName>
<desc><address><addrLine>Campus de Beaulieu 35042 Rennes cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/asap</ref>
</desc>
<listRelation><relation active="#struct-419153" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-490900" type="direct"></relation>
<relation active="#struct-490899" type="indirect"></relation>
<relation active="#struct-105160" type="indirect"></relation>
<relation active="#struct-117606" type="indirect"></relation>
<relation active="#struct-172265" type="indirect"></relation>
<relation active="#struct-247362" type="indirect"></relation>
<relation active="#struct-411575" type="indirect"></relation>
<relation name="UMR6074" active="#struct-441569" type="indirect"></relation>
<relation active="#struct-481355" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-419153" type="direct"><org type="laboratory" xml:id="struct-419153" status="VALID"><idno type="RNSR">198018249C</idno>
<orgName>Inria Rennes – Bretagne Atlantique </orgName>
<desc><address><addrLine>Campus de beaulieu35042 Rennes cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/centre/rennes</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-490900" type="direct"><org type="department" xml:id="struct-490900" status="VALID"><orgName>SYSTÈMES LARGE ÉCHELLE</orgName>
<orgName type="acronym">IRISA_D1</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">https://www.irisa.fr/fr/departements/d1-systemes-large-echelle</ref>
</desc>
<listRelation><relation active="#struct-490899" type="direct"></relation>
<relation active="#struct-105160" type="indirect"></relation>
<relation active="#struct-117606" type="indirect"></relation>
<relation active="#struct-172265" type="indirect"></relation>
<relation active="#struct-247362" type="indirect"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-411575" type="indirect"></relation>
<relation name="UMR6074" active="#struct-441569" type="indirect"></relation>
<relation active="#struct-481355" type="indirect"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-490899" type="indirect"><org type="laboratory" xml:id="struct-490899" status="VALID"><idno type="IdRef">026386909</idno>
<idno type="ISNI">0000 0001 2298 7270</idno>
<idno type="RNSR">200012163A</idno>
<orgName>Institut de Recherche en Informatique et Systèmes Aléatoires</orgName>
<orgName type="acronym">IRISA</orgName>
<date type="start">2017-01-01</date>
<desc><address><addrLine>Avenue du général LeclercCampus de Beaulieu 35042 RENNES CEDEX</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.irisa.fr</ref>
</desc>
<listRelation><relation active="#struct-105160" type="direct"></relation>
<relation active="#struct-117606" type="direct"></relation>
<relation active="#struct-172265" type="direct"></relation>
<relation active="#struct-247362" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-411575" type="direct"></relation>
<relation name="UMR6074" active="#struct-441569" type="direct"></relation>
<relation active="#struct-481355" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-105160" type="indirect"><org type="institution" xml:id="struct-105160" status="VALID">          <orgName>Université de Rennes 1</orgName>
          <orgName type="acronym">UR1</orgName>
          <desc>            <address>              <addrLine>2 rue du Thabor - CS 46510 - 35065 Rennes cedex</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univ-rennes1.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-117606" type="indirect"><org type="institution" xml:id="struct-117606" status="VALID">          <orgName>Institut National des Sciences Appliquées - Rennes</orgName>
          <orgName type="acronym">INSA Rennes</orgName>
          <desc>            <address>              <addrLine>20, avenue des Buttes de Coësmes - CS 70839 - 35708 Rennes cedex 7</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.insa-rennes.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-172265" type="indirect"><org type="institution" xml:id="struct-172265" status="VALID">          <orgName>Université de Bretagne Sud</orgName>
          <orgName type="acronym">UBS</orgName>
          <desc>            <address>              <addrLine>BP 92116 - 56321 Lorient cedex</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univ-ubs.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-247362" type="indirect"><org type="institution" xml:id="struct-247362" status="VALID">          <orgName>École normale supérieure - Rennes</orgName>
          <orgName type="acronym">ENS Rennes</orgName>
          <desc>            <address>              <addrLine>Campus de Ker Lann - avenue Robert Schuman - 35170 Bruz</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.ens-rennes.fr</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-411575" type="indirect"><org type="institution" xml:id="struct-411575" status="VALID"><orgName>CentraleSupélec</orgName>
<desc><address><addrLine>3, rue Joliot Curie,Plateau de Moulon,91192 GIF-SUR-YVETTE Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.centralesupelec.fr</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR6074" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID">          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.cnrs.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-481355" type="indirect"><org type="institution" xml:id="struct-481355" status="VALID"><orgName>IMT Atlantique Bretagne-Pays de la Loire</orgName>
<orgName type="acronym">IMT Atlantique</orgName>
<date type="start">2017-01-01</date>
<desc><address><addrLine>Campus Brest : Technopôle Brest-Iroise CS 8381829238 BREST Cedex 3 -Campus Nantes : 4, rue Alfred Kastler- La chantrerie 44300 NANTES -Campus Rennes :  2 Rue de la Châtaigneraie, 35510 CESSON SEVIGNE</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Rennes</settlement>
<region type="region" nuts="2">Région Bretagne</region>
</placeName>
<orgName type="university">Université de Rennes 1</orgName>
<orgName type="institution" wicri:auto="newGroup">Université européenne de Bretagne</orgName>
<placeName><settlement type="city">Lorient</settlement>
<region type="region" nuts="2">Région Bretagne</region>
</placeName>
<orgName type="university">Université de Bretagne-Sud</orgName>
<orgName type="institution" wicri:auto="newGroup">Université européenne de Bretagne</orgName>
</affiliation>
</author>
<author><name sortKey="Haeupler, Bernhard" sort="Haeupler, Bernhard" uniqKey="Haeupler B" first="Bernhard" last="Haeupler">Bernhard Haeupler</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-87723" status="VALID">          <orgName>Computer Science Department - Carnegie Mellon University</orgName>
          <desc>            <address>              <addrLine>Computer Science Department Carnegie Mellon University Pittsburgh, PA</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.cs.cmu.edu/</ref>
          </desc>
          <listRelation>            <relation active="#struct-378064" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-378064" type="direct"><org type="institution" xml:id="struct-378064" status="INCOMING">          <orgName>University of Pittsburgh</orgName>
          <desc>            <address>              <country key="FR"></country>
            </address>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
<placeName><settlement type="city">Pittsburgh</settlement>
<region type="state">Pennsylvanie</region>
</placeName>
<orgName type="university">Université de Pittsburgh</orgName>
</affiliation>
</author>
<author><name sortKey="Kuhn, Fabian" sort="Kuhn, Fabian" uniqKey="Kuhn F" first="Fabian" last="Kuhn">Fabian Kuhn</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-56846" status="VALID"><orgName>Department of Computer Science [Freiburg]</orgName>
<desc><address><addrLine>Georges-Kohler-Allee 79, 79108 Freiburg, Germany</addrLine>
<country key="DE"></country>
</address>
<ref type="url">http://www.informatik.uni-freiburg.de/</ref>
</desc>
<listRelation><relation active="#struct-68615" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-68615" type="direct"><org type="institution" xml:id="struct-68615" status="VALID"><orgName>University of Freiburg [Freiburg]</orgName>
<desc><address><addrLine>Friedrichstr. 39 79098 Freiburg</addrLine>
<country key="DE"></country>
</address>
<ref type="url">http://www.uni-freiburg.de/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Allemagne</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-01635743</idno>
<idno type="halId">hal-01635743</idno>
<idno type="halUri">https://hal.inria.fr/hal-01635743</idno>
<idno type="url">https://hal.inria.fr/hal-01635743</idno>
<idno type="doi">10.1145/3086465</idno>
<date when="2017-05-29">2017-05-29</date>
<idno type="wicri:Area/Hal/Corpus">000641</idno>
<idno type="wicri:Area/Hal/Curation">000641</idno>
<idno type="wicri:Area/Hal/Checkpoint">000014</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">000014</idno>
<idno type="wicri:doubleKey">1549-6325:2017:Censor Hillel K:tight:bounds:on</idno>
<idno type="wicri:Area/Main/Merge">000014</idno>
<idno type="wicri:Area/Main/Curation">000014</idno>
<idno type="wicri:Area/Main/Exploration">000014</idno>
<idno type="wicri:Area/France/Extraction">000012</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Tight Bounds on Vertex Connectivity Under Sampling</title>
<author><name sortKey="Censor Hillel, Keren" sort="Censor Hillel, Keren" uniqKey="Censor Hillel K" first="Keren" last="Censor-Hillel">Keren Censor-Hillel</name>
<affiliation wicri:level="1"><hal:affiliation type="department" xml:id="struct-425640" status="VALID"><orgName>Department of Computer Science [Haifa]</orgName>
<date type="start">2015-08-14</date>
<desc><address><addrLine>TechnionIsrael Institute of TechnologyHaifa 32000Israel</addrLine>
<country key="IL"></country>
</address>
<ref type="url">http://www.cs.technion.ac.il/</ref>
</desc>
<listRelation><relation active="#struct-84142" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-84142" type="direct"><org type="institution" xml:id="struct-84142" status="VALID">          <orgName>Technion - Israel Institute of Technology [Haifa]</orgName>
          <desc>            <address>              <addrLine>Technion City, Haifa 3200003</addrLine>
              <country key="IL"></country>
            </address>
            <ref type="url">http://www1.technion.ac.il/en</ref>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Israël</country>
</affiliation>
</author>
<author><name sortKey="Ghaffari, Mohsen" sort="Ghaffari, Mohsen" uniqKey="Ghaffari M" first="Mohsen" last="Ghaffari">Mohsen Ghaffari</name>
<affiliation wicri:level="1"><hal:affiliation type="institution" xml:id="struct-301950" status="VALID">          <orgName>Massachusetts Institute of Technology</orgName>
          <orgName type="acronym">MIT</orgName>
          <desc>            <address>              <addrLine>77 Massachusetts Ave, Cambridge, MA 02139</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://web.mit.edu</ref>
          </desc>
        </hal:affiliation>
<country>États-Unis</country>
</affiliation>
</author>
<author><name sortKey="Giakkoupis, George" sort="Giakkoupis, George" uniqKey="Giakkoupis G" first="George" last="Giakkoupis">George Giakkoupis</name>
<affiliation wicri:level="1"><hal:affiliation type="researchteam" xml:id="struct-490904" status="VALID"><idno type="RNSR">200718348T</idno>
<orgName>As Scalable As Possible: foundations of large scale dynamic distributed systems</orgName>
<orgName type="acronym">ASAP</orgName>
<desc><address><addrLine>Campus de Beaulieu 35042 Rennes cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/equipes/asap</ref>
</desc>
<listRelation><relation active="#struct-419153" type="direct"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-490900" type="direct"></relation>
<relation active="#struct-490899" type="indirect"></relation>
<relation active="#struct-105160" type="indirect"></relation>
<relation active="#struct-117606" type="indirect"></relation>
<relation active="#struct-172265" type="indirect"></relation>
<relation active="#struct-247362" type="indirect"></relation>
<relation active="#struct-411575" type="indirect"></relation>
<relation name="UMR6074" active="#struct-441569" type="indirect"></relation>
<relation active="#struct-481355" type="indirect"></relation>
</listRelation>
<tutelles><tutelle active="#struct-419153" type="direct"><org type="laboratory" xml:id="struct-419153" status="VALID"><idno type="RNSR">198018249C</idno>
<orgName>Inria Rennes – Bretagne Atlantique </orgName>
<desc><address><addrLine>Campus de beaulieu35042 Rennes cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/centre/rennes</ref>
</desc>
<listRelation><relation active="#struct-300009" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-300009" type="indirect"><org type="institution" xml:id="struct-300009" status="VALID"><orgName>Institut National de Recherche en Informatique et en Automatique</orgName>
<orgName type="acronym">Inria</orgName>
<desc><address><addrLine>Domaine de VoluceauRocquencourt - BP 10578153 Le Chesnay Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.inria.fr/en/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-490900" type="direct"><org type="department" xml:id="struct-490900" status="VALID"><orgName>SYSTÈMES LARGE ÉCHELLE</orgName>
<orgName type="acronym">IRISA_D1</orgName>
<desc><address><country key="FR"></country>
</address>
<ref type="url">https://www.irisa.fr/fr/departements/d1-systemes-large-echelle</ref>
</desc>
<listRelation><relation active="#struct-490899" type="direct"></relation>
<relation active="#struct-105160" type="indirect"></relation>
<relation active="#struct-117606" type="indirect"></relation>
<relation active="#struct-172265" type="indirect"></relation>
<relation active="#struct-247362" type="indirect"></relation>
<relation active="#struct-300009" type="indirect"></relation>
<relation active="#struct-411575" type="indirect"></relation>
<relation name="UMR6074" active="#struct-441569" type="indirect"></relation>
<relation active="#struct-481355" type="indirect"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-490899" type="indirect"><org type="laboratory" xml:id="struct-490899" status="VALID"><idno type="IdRef">026386909</idno>
<idno type="ISNI">0000 0001 2298 7270</idno>
<idno type="RNSR">200012163A</idno>
<orgName>Institut de Recherche en Informatique et Systèmes Aléatoires</orgName>
<orgName type="acronym">IRISA</orgName>
<date type="start">2017-01-01</date>
<desc><address><addrLine>Avenue du général LeclercCampus de Beaulieu 35042 RENNES CEDEX</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.irisa.fr</ref>
</desc>
<listRelation><relation active="#struct-105160" type="direct"></relation>
<relation active="#struct-117606" type="direct"></relation>
<relation active="#struct-172265" type="direct"></relation>
<relation active="#struct-247362" type="direct"></relation>
<relation active="#struct-300009" type="direct"></relation>
<relation active="#struct-411575" type="direct"></relation>
<relation name="UMR6074" active="#struct-441569" type="direct"></relation>
<relation active="#struct-481355" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-105160" type="indirect"><org type="institution" xml:id="struct-105160" status="VALID">          <orgName>Université de Rennes 1</orgName>
          <orgName type="acronym">UR1</orgName>
          <desc>            <address>              <addrLine>2 rue du Thabor - CS 46510 - 35065 Rennes cedex</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univ-rennes1.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-117606" type="indirect"><org type="institution" xml:id="struct-117606" status="VALID">          <orgName>Institut National des Sciences Appliquées - Rennes</orgName>
          <orgName type="acronym">INSA Rennes</orgName>
          <desc>            <address>              <addrLine>20, avenue des Buttes de Coësmes - CS 70839 - 35708 Rennes cedex 7</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.insa-rennes.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-172265" type="indirect"><org type="institution" xml:id="struct-172265" status="VALID">          <orgName>Université de Bretagne Sud</orgName>
          <orgName type="acronym">UBS</orgName>
          <desc>            <address>              <addrLine>BP 92116 - 56321 Lorient cedex</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.univ-ubs.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-247362" type="indirect"><org type="institution" xml:id="struct-247362" status="VALID">          <orgName>École normale supérieure - Rennes</orgName>
          <orgName type="acronym">ENS Rennes</orgName>
          <desc>            <address>              <addrLine>Campus de Ker Lann - avenue Robert Schuman - 35170 Bruz</addrLine>
              <country key="FR"></country>
            </address>
            <ref type="url">http://www.ens-rennes.fr</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-411575" type="indirect"><org type="institution" xml:id="struct-411575" status="VALID"><orgName>CentraleSupélec</orgName>
<desc><address><addrLine>3, rue Joliot Curie,Plateau de Moulon,91192 GIF-SUR-YVETTE Cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.centralesupelec.fr</ref>
</desc>
</org>
</tutelle>
<tutelle name="UMR6074" active="#struct-441569" type="indirect"><org type="institution" xml:id="struct-441569" status="VALID">          <idno type="IdRef">02636817X</idno>
          <idno type="ISNI">0000000122597504</idno>
          <orgName>Centre National de la Recherche Scientifique</orgName>
          <orgName type="acronym">CNRS</orgName>
          <date type="start">1939-10-19</date>
          <desc>            <address>              <country key="FR"></country>
            </address>
            <ref type="url">http://www.cnrs.fr/</ref>
          </desc>
        </org>
</tutelle>
<tutelle active="#struct-481355" type="indirect"><org type="institution" xml:id="struct-481355" status="VALID"><orgName>IMT Atlantique Bretagne-Pays de la Loire</orgName>
<orgName type="acronym">IMT Atlantique</orgName>
<date type="start">2017-01-01</date>
<desc><address><addrLine>Campus Brest : Technopôle Brest-Iroise CS 8381829238 BREST Cedex 3 -Campus Nantes : 4, rue Alfred Kastler- La chantrerie 44300 NANTES -Campus Rennes :  2 Rue de la Châtaigneraie, 35510 CESSON SEVIGNE</addrLine>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>France</country>
<placeName><settlement type="city">Rennes</settlement>
<region type="region" nuts="2">Région Bretagne</region>
</placeName>
<orgName type="university">Université de Rennes 1</orgName>
<orgName type="institution" wicri:auto="newGroup">Université européenne de Bretagne</orgName>
<placeName><settlement type="city">Lorient</settlement>
<region type="region" nuts="2">Région Bretagne</region>
</placeName>
<orgName type="university">Université de Bretagne-Sud</orgName>
<orgName type="institution" wicri:auto="newGroup">Université européenne de Bretagne</orgName>
</affiliation>
</author>
<author><name sortKey="Haeupler, Bernhard" sort="Haeupler, Bernhard" uniqKey="Haeupler B" first="Bernhard" last="Haeupler">Bernhard Haeupler</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-87723" status="VALID">          <orgName>Computer Science Department - Carnegie Mellon University</orgName>
          <desc>            <address>              <addrLine>Computer Science Department Carnegie Mellon University Pittsburgh, PA</addrLine>
              <country key="US"></country>
            </address>
            <ref type="url">http://www.cs.cmu.edu/</ref>
          </desc>
          <listRelation>            <relation active="#struct-378064" type="direct"></relation>
          </listRelation>
        <tutelles><tutelle active="#struct-378064" type="direct"><org type="institution" xml:id="struct-378064" status="INCOMING">          <orgName>University of Pittsburgh</orgName>
          <desc>            <address>              <country key="FR"></country>
            </address>
          </desc>
        </org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>États-Unis</country>
<placeName><settlement type="city">Pittsburgh</settlement>
<region type="state">Pennsylvanie</region>
</placeName>
<orgName type="university">Université de Pittsburgh</orgName>
</affiliation>
</author>
<author><name sortKey="Kuhn, Fabian" sort="Kuhn, Fabian" uniqKey="Kuhn F" first="Fabian" last="Kuhn">Fabian Kuhn</name>
<affiliation wicri:level="1"><hal:affiliation type="laboratory" xml:id="struct-56846" status="VALID"><orgName>Department of Computer Science [Freiburg]</orgName>
<desc><address><addrLine>Georges-Kohler-Allee 79, 79108 Freiburg, Germany</addrLine>
<country key="DE"></country>
</address>
<ref type="url">http://www.informatik.uni-freiburg.de/</ref>
</desc>
<listRelation><relation active="#struct-68615" type="direct"></relation>
</listRelation>
<tutelles><tutelle active="#struct-68615" type="direct"><org type="institution" xml:id="struct-68615" status="VALID"><orgName>University of Freiburg [Freiburg]</orgName>
<desc><address><addrLine>Friedrichstr. 39 79098 Freiburg</addrLine>
<country key="DE"></country>
</address>
<ref type="url">http://www.uni-freiburg.de/</ref>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
<country>Allemagne</country>
</affiliation>
</author>
</analytic>
<idno type="DOI">10.1145/3086465</idno>
<series><title level="j">ACM Transactions on Algorithms</title>
<idno type="ISSN">1549-6325</idno>
<imprint><date type="datePub">2017-05-29</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">A fundamental result by Karger [10] states that for any $λ$-edge-connected graph with n nodes, independently sampling each edge with probability $p = Ω(log(n)/λ)$ results in a graph that has edge connectivity $Ω(λp)$, with high probability. This paper proves the analogous result for vertex connectivity, when either vertices or edges are sampled. We show that for any k-vertex-connected graph G with n nodes, if each node is independently sampled with probability $p = Ω(log(n)/k)$, then the subgraph induced by the sampled nodes has vertex connectivity $Ω(kp 2$), with high probability. If edges are sampled with probability $p = Ω(log(n)/k)$ then the sampled subgraph has vertex connectivity $Ω(kp$), with high probability. Both bounds are existentially optimal.</div>
</front>
</TEI>
<affiliations><list><country><li>Allemagne</li>
<li>France</li>
<li>Israël</li>
<li>États-Unis</li>
</country>
<region><li>Pennsylvanie</li>
<li>Région Bretagne</li>
</region>
<settlement><li>Lorient</li>
<li>Pittsburgh</li>
<li>Rennes</li>
</settlement>
<orgName><li>Université de Bretagne-Sud</li>
<li>Université de Pittsburgh</li>
<li>Université de Rennes 1</li>
<li>Université européenne de Bretagne</li>
</orgName>
</list>
<tree><country name="Israël"><noRegion><name sortKey="Censor Hillel, Keren" sort="Censor Hillel, Keren" uniqKey="Censor Hillel K" first="Keren" last="Censor-Hillel">Keren Censor-Hillel</name>
</noRegion>
</country>
<country name="États-Unis"><noRegion><name sortKey="Ghaffari, Mohsen" sort="Ghaffari, Mohsen" uniqKey="Ghaffari M" first="Mohsen" last="Ghaffari">Mohsen Ghaffari</name>
</noRegion>
<name sortKey="Haeupler, Bernhard" sort="Haeupler, Bernhard" uniqKey="Haeupler B" first="Bernhard" last="Haeupler">Bernhard Haeupler</name>
</country>
<country name="France"><region name="Région Bretagne"><name sortKey="Giakkoupis, George" sort="Giakkoupis, George" uniqKey="Giakkoupis G" first="George" last="Giakkoupis">George Giakkoupis</name>
</region>
</country>
<country name="Allemagne"><noRegion><name sortKey="Kuhn, Fabian" sort="Kuhn, Fabian" uniqKey="Kuhn F" first="Fabian" last="Kuhn">Fabian Kuhn</name>
</noRegion>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Amérique/explor/PittsburghV1/Data/France/Analysis

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000012 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/France/Analysis/biblio.hfd -nk 000012 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Amérique
   |area=    PittsburghV1
   |flux=    France
   |étape=   Analysis
   |type=    RBID
   |clé=     Hal:hal-01635743
   |texte=   Tight Bounds on Vertex Connectivity Under Sampling
}}

This area was generated with Dilib version V0.6.38.
Data generation: Fri Jun 18 17:37:45 2021. Site generation: Fri Jun 18 18:15:47 2021

	Serveur d'exploration sur Pittsburgh
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur Pittsburgh

Tight Bounds on Vertex Connectivity Under Sampling

Tight Bounds on Vertex Connectivity Under Sampling

Source :

Abstract

Links toward previous steps (curation, corpus...)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri